1. Field of the Invention
The present invention generally relates to data processing, and more specifically, the invention relates to graphics processing using a plurality of rendering servers. Even more specifically, the invention relates to managing graphic load balancing strategies for the rendering servers.
2. Background Art
Computer applications have been developed that present graphic-intensive data processing, including real time video animation in which an image may be refreshed at rates up to thirty times a second. The presentation of such information can often strain the abilities of a computer system, since it may take a significant amount of processing work for the computer system to refresh the display screen at the desired rate.
One strategy for handling this workload is to utilize multiple concurrent rendering processors to perform animation. A computer program can be separated into a collection of processes that are executed by the processors. One possible way in which the work may be distributed among the available rendering processors is to subdivide the display into multiple regions, referred to as tiles, and then assign one or more tiles to each process.
Increasingly, computer graphic systems are being designed, constructed, and utilized that employ a collection or cluster of rendering servers to render to either a single display or to some sort of “tiled” display (comprised of multiple logical or practical displays). These clustered rendering systems are increasing in popularity due to the availability of their commodity components and their ability to effectively use the aggregation of the servers' resources. However, care must be taken to ensure that the resources of each individual server are being efficiently used.
For example, any application running on such a clustered rendering system should adjust the distribution of its rendering tasks to the individual rendering servers so that there is not an appreciable load imbalance between the rendering servers. Such an imbalance has the potential to limit the performance and utility of the overall application.
Strategies for distributing data have been developed so that the appropriate data is sent to and rendered by the rendering server that is attached to the display, on which, the rendered data will be viewed. This approach, commonly referred to as the “sort-first” distribution strategy, has proven to be effective at taking advantage of the rendering capability of each server and balancing out the rendering load fairly well, especially for relatively static scenes where the data is evenly distributed across the displays and their associated servers.
However, if the scene is manipulated in such a way that large portions of the data can fall in the boundaries of one or a few displays, it readily becomes apparent that simply redistributing the data to the appropriate rendering server is no longer sufficient. In these scenarios, due to the fact that rendered pixels of the data all resides on a minority of the displays, then only a minority of the rendering servers will be doing any work while the other servers sit idle.
To address these situations, several researchers have developed techniques for dynamically partitioning the display regions so that these smaller partitions can be assigned so that servers that were doing little to no work in the previous frame can now be given regions of the display to render that require a lot of work. These techniques distribute the rendering loads more evenly and require feedback from the rendering servers in order to perform their repartitioning and reassignments. Typically, this feedback is in the form of performance measurements such as the time it takes a server to send its data to another server or the time it takes a server to render and display its data. If these performance values exceed a particular threshold, the rebalancing algorithms are triggered.
Each of these balancing “policies” differ in the way they partition the screen space or “tiles,” which performance metrics they evaluate, and how they use these metrics to “rebalance” the screen and reassign partitions and data to other nodes. Although each of these policies is effective for certain scenarios, there are scenarios where they are not effective and other policies are warranted. These scenario characteristics include (but are not limited to): size and nature of the data to be rendered, size of the display to be rendered to, single display vs. tiled display, number of display attached rendering servers vs. “stand-alone” (rendering servers which will ship their resulting pixels to a server attached to a display), application usage patterns, and number of total rendering servers.
Each of these characteristics can significantly affect the efficiency of each individual load balancing policy. Samanta, et al, in “Load Balancing for multi-projector systems,” Graphics Hardware 1999, pp 107-116. describe this behavior in the experimental testing of their own load balancing algorithms. Consequently, if one were to design a system for doing efficient and high performing distributed rendering that was adaptable to both the hardware and software characteristics of the applications to be run or the cluster unit that it is running on, there needs to be a mechanism in place to change the load balancing policy. A system that was able to change the load balancing policy in real-time and according to the user's discretion or based on the nature of the application and resource environment would be at a significant utility advantage to those systems that are unable to adapt appropriately.